//回⽂串分割IV（hard）: https://leetcode.cn/problems/palindrome-partitioning-iv/
class Solution {
public:
 bool checkPartitioning(string s
 {
        // 1. ⽤ dp 把所有的⼦串是否是回⽂预处理⼀下
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n));
        for (int i = n - 1; i >= 0; i--)
            for (int j = i; j < n; j++)
                if (s[i] == s[j])
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
        // 2. 枚举所有的第⼆个字符串的起始位置以及结束位置
        for (int i = 1; i < n - 1; i++)
            for (int j = i; j < n - 1; j++)
                if (dp[0][i - 1] && dp[i][j] && dp[j + 1][n - 1])
                    return true;
        return false;
 }
};

//分割回⽂串II（hard）: https://leetcode.cn/problems/palindrome-partitioning-ii/description/
class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        vector<vector<bool>> isPal(n,
                                   vector<bool>(n)); // 统计所有⼦串是否是回⽂
        for (int i = n - 1; i >= 0; i--)
            for (int j = i; j < n; j++)
                isPal[i][j] = s[i] == s[j] ? (i + 1 < j ? isPal[i + 1][j - 1] : true) : false;

        vector<int> dp(n, INT_MAX);
        for (int i = 0; i < n; i++) {
            if (isPal[0][i])
                dp[i] = 0;
            else {
                for (int j = 1; j <= i; j++)
                    if (isPal[j][i])
                        dp[i] = min(dp[i], dp[j - 1] + 1);
            }
        }
        return dp[n - 1];
    }
};
